# -*- encoding: utf-8 -*-

initial_grid = [
    [3, 0, 6, 5, 0, 8, 4, 0, 0],
    [5, 2, 0, 0, 0, 0, 0, 0, 0],
    [0, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]

no_solution = [
    [5, 0, 6, 5, 0, 8, 4, 0, 3],
    [5, 2, 0, 0, 0, 0, 0, 0, 2],
    [1, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]

solutions = []


def is_complete(grid):
    for i in grid:
        for j in i:
            if j == 0:
                return False
    return True


def find_empty_location(grid):
    for i in range(len(grid)):
        for j in range(len(grid)):
            if grid[i][j] == 0:
                return i, j


def is_safe(grid, row, column, digit):
    for i in range(len(grid)):
        if grid[row][i] == digit or grid[i][column] == digit:
            return False

    for i in range(3):
        for j in range(3):
            if grid[(row - row % 3) + i][(column - column % 3) + j] == digit:
                return False

    return True


def sudoku(grid):
    if is_complete(grid):
        solutions.append(grid)
        # print_solution(grid)
        # print()
        return

    row, column = find_empty_location(grid)

    for digit in range(1, 10):
        if is_safe(grid, row, column, digit):
            grid[row][column] = digit
            sudoku(grid)
            grid[row][column] = 0

    return False


def print_solution(grid):
    for i in grid:
        for j in i:
            print(j, end=' ')
        print()


if __name__ == '__main__':
    for grid in (initial_grid, no_solution):
        solutions = []
        grid = list(map(list, grid))
        sudoku(grid)
        if solutions:
            print("grid after solving:")
            print('solve plan: ', len(solutions))
            for s in solutions:
                print_solution(s)
                print()
        else:
            print("Cannot find a solution.")
